#include <iostream>
#include <sstream>
#include <set>
#include <unordered_set>
#include <map>

#include <vector>
#include <algorithm>


// support for multi-thread processing
#include <mutex>
#include "utils/ThreadPool.hpp"
#include "utils/util.h"

#define NULL_NODE -1


template<class VD, class ED>
class state {

	/**
	 * Optimazations are applied, including:
	 *	1. pattern matching order support;
	 *	2. filtering vertices with unrelated labels;
	 *	3. using signatures in the matching check;
	 */

public:

	//constructor1
	state(Query<VD, ED>* _g1, int _v1, Fragment<VD, ED>* _g2, const int _v2, std::map<int, int>& core1r, std::map<int, int>& core2r,
	      std::map<int, int>& in1r, std::map<int, int>& in2r, std::map<int, int>& out1r, std::map<int, int>& out2r, std::vector<int>& sn2r, std::set<int>& sn2kr, std::set<int>& labelr):
		g1(_g1), g2(_g2) {

		gs1 = g1->getNumVertices();
		gs2 = g2->getNumVertices();

		core_len = 0;
		orig_core_len = 0;
		t1both_len = 0;
		t1in_len = 0;
		t1out_len = 0;
		t2both_len = 0;
		t2in_len = 0;
		t2out_len = 0;

		added_n1 = NULL_NODE;

		// init real entity
		sn2r.push_back(_v2);
		sn2kr.insert(_v2);

		// init the pointers
		core1 = &core1r;
		core2 = &core2r;
		in1 = &in1r;
		in2 = &in2r;
		out1 = &out1r;
		out2 = &out2r;

		sn2 = &sn2r;
		sn2k = &sn2kr;
		labels = &labelr;
	}

	//constructor2 copy
	state(const state<VD, ED>& copy) {

		// cout<<"copy a state"<<std::endl;
		g1 = copy.g1;
		g2 = copy.g2;

		core_len = copy.core_len;
		orig_core_len = copy.orig_core_len;

		t1both_len = copy.t1both_len;
		t2both_len = copy.t2both_len;
		t1in_len = copy.t1in_len;
		t2in_len = copy.t2in_len;
		t1out_len = copy.t1out_len;
		t2out_len = copy.t2out_len;

		gs1 = copy.gs1;
		gs2 = copy.gs2;

		added_n1 = NULL_NODE;
		std::vector<int> added_seen_n2;

		// NOTE: we don't need to copy these arrays because their state restored
		// via the backTrack() function after processing on the cloned state
		// finishes
		core1 = copy.core1;
		core2 = copy.core2;
		in1 = copy.in1;
		in2 = copy.in2;
		out1 = copy.out1;
		out2 = copy.out2;

		sn2 = copy.sn2;
		sn2k = copy.sn2k;
		labels = copy.labels;
	}

	bool areCompatibleEdges(int v1, int v2, int v3, int v4) {
		return true;
	}

	bool areCompatableVertices(int v1, int v2) {
		return g1->getVertexAttr(v1) == g2->getVertexAttr(v2) &&
		       match(g1->getSignature(OUT_R1, v1), g2->getSignature(OUT_R1, v2)) &&
		       match(g1->getSignature(IN_R1, v1), g2->getSignature(IN_R1, v2)) &&
		       match(g1->getSignature(OUT_R2, v1), g2->getSignature(OUT_R2, v2)) &&
		       match(g1->getSignature(IN_R2, v1), g2->getSignature(IN_R2, v2));
		//return true;
	}

	std::pair<int, int> nextPair(int prev_n1, int prev_n2) {

		if (prev_n1 == NULL_NODE) {
			prev_n1 = 0;
		}

		if (prev_n2 == NULL_NODE)
			prev_n2 = 0;

		else {
			prev_n2 = get_index(sn2, prev_n2);
			prev_n2++;
			while (prev_n2 < sn2->size()
			        && (contains(core2, sn2->at(prev_n2))
			            || !contains(out2, sn2->at(prev_n2)))
			        && (contains(core2, sn2->at(prev_n2))
			            || !contains(in2, sn2->at(prev_n2)))) {
				prev_n2++;
			}
		}

		if (t1both_len > core_len && t2both_len > core_len) {

			while (prev_n1 < gs1
			        && (contains(core1, prev_n1) || !contains(out1, prev_n1)
			            || !contains(in1, prev_n1))) {
				prev_n1++;
				prev_n2 = 0;
			}
			while (prev_n2 < sn2->size()
			        && (contains(core2, sn2->at(prev_n2))
			            || !contains(out2, sn2->at(prev_n2))
			            || !contains(in2, sn2->at(prev_n2)))) {
				prev_n2++;
			}
		} else if (t1out_len > core_len && t2out_len > core_len) {
			while (prev_n1 < gs1
			        && (contains(core1, prev_n1) || !contains(out1, prev_n1))) {
				prev_n1++;
				prev_n2 = 0;
			}
			while (prev_n2 < sn2->size()
			        && (contains(core2, sn2->at(prev_n2))
			            || !contains(out2, sn2->at(prev_n2)))) {
				prev_n2++;
			}

		} else if (t1in_len > core_len && t2in_len > core_len) {
			while (prev_n1 < gs1
			        && (contains(core1, prev_n1) || !contains(in1, prev_n1))) {
				prev_n1++;
				prev_n2 = 0;
			}
			while (prev_n2 < sn2->size()
			        && (contains(core2, sn2->at(prev_n2))
			            || !contains(in2, sn2->at(prev_n2)))) {
				prev_n2++;
			}
		} else {
			while (prev_n1 < gs1 && contains(core1, prev_n1)) {
				prev_n1++;
				prev_n2 = 0;
			}
			while (prev_n2 < sn2->size() && contains(core2, sn2->at(prev_n2))) {
				prev_n2++;
			}
		}

		if (prev_n1 < gs1 && prev_n2 < sn2->size()) {
			return std::make_pair(prev_n1, sn2->at(prev_n2));
		} else
			return std::make_pair(NULL_NODE, NULL_NODE);
	}

	bool isFeasiblePair(int node1, int node2) {

//			assert node1 < n1;
//			assert !core1.containsKey(node1);

		if (!areCompatableVertices(node1, node2)) {
			return false;
		}

		int termout1 = 0, termout2 = 0, termin1 = 0, termin2 = 0, new1 = 0,
		    new2 = 0;

		// Check the 'out' edges of node1
		for (int other1 : g1->getChildrenID(node1)) {
			if (contains(core1, other1)) {
				int other2 = core1->at(other1);
				// If there's node edge to the other node, or if there is some
				// edge incompatibility, then the std::unordered_mapping is not feasible
				if (!g2->existEdge(node2, other2)
				        || !areCompatibleEdges(node1, other1, node2, other2)) {
					return false;
				}
			} else {
				if (contains(in1, other1))
					termin1++;
				if (contains(out1, other1))
					termout1++;
				if ((!contains(in1, other1)) && (!contains(out1, other1)))
					new1++;
			}
		}

		// Check the 'in' edges of node1
		for (int other1 : g1->getParentsID(node1)) {
			if (contains(core1, other1)) {
				int other2 = core1->at(other1);
				// If there's node edge to the other node, or if there is some
				// edge incompatibility, then the std::unordered_mapping is not feasible
				if (!g2->existEdge(other2, node2)
				        || !areCompatibleEdges(other1, node1, other2, node2)) {
					return false;
				}
			} else {
				if (contains(in1, other1))
					termin1++;
				if (contains(out1, other1))
					termout1++;
				if ((!contains(in1, other1)) && (!contains(out1, other1)))
					new1++;
			}
		}

		// Check the 'out' edges of node2
		for (int other2 : g2->getChildrenID(node2)) {
			// if (contains(core2, other2)) {
			// 	int other1 = core2->at(other2);
			// 	// If there's node edge to the other node, or if there is some
			// 	// edge incompatibility, then the std::unordered_mapping is not feasible
			// 	if (!g1->existEdge(node1, other1)
			// 	        || !areCompatibleEdges(node1, other1, node2, other2)) {
			// 		return false;
			// 	}
			// } else {
			if (!contains(core2, other2)) {
				if (contains(in2, other2))
					termin2++;
				if (contains(out2, other2))
					termout2++;
				if ((!contains(in2, other2)) && (!contains(out2, other2)))
					new2++;
			}
		}

		// Check the 'in' edges of node2
		for (int other2 : g2->getParentsID(node2)) {
			// if (contains(core2, other2)) {
			// 	int other1 = core2->at(other2);
			// 	// If there's node edge to the other node, or if there is some
			// 	// edge incompatibility, then the std::unordered_mapping is not feasible
			// 	if (!g1->existEdge(other1, node1)
			// 	        || !areCompatibleEdges(other1, node1, other2, node2)) {
			// 		return false;
			// 	}
			// } else {
			if (!contains(core2, other2)){
				if (contains(in2, other2))
					termin2++;
				if (contains(out2, other2))
					termout2++;
				if ((!contains(in2, other2)) && (!contains(out2, other2)))
					new2++;
			}
		}

		return termin1 <= termin2 && termout1 <= termout2 && new1 <= new2;
	}

	void addPair(int node1, int node2) {
//			assert node1 < n1;
//			assert coreLen < n1;

		core_len++;
		added_n1 = node1;

		if (!contains(in1, node1)) {
			in1->insert(std::make_pair(node1, core_len));
			t1in_len++;
			if (contains(out1, node1))
				t1both_len++;
		}
		if (!contains(out1, node1)) {
			out1->insert(std::make_pair(node1, core_len));
			t1out_len++;
			if (contains(in1, node1))
				t1both_len++;
		}

		if (!contains(in2, node2)) {
			in2->insert(std::make_pair(node2, core_len));
			t2in_len++;
			if (contains(out2, node2))
				t2both_len++;
		}
		if (!contains(out2, node2)) {
			out2->insert(std::make_pair(node2, core_len));
			t2out_len++;
			if (contains(in2, node2))
				t2both_len++;
		}

		core1->insert(std::make_pair(node1, node2));
		core2->insert(std::make_pair(node2, node1));


		for (int other : g1->getParentsID(node1)) {

			// int otherlabel = g1->getVertexAttr(other);

			// filtermap_parent_in1[otherlabel].push_back(g1->getSig(IN_R1, other));
			// filtermap_parent_out1[otherlabel].push_back(g1->getSig(OUT_R1, other));
			// filtermap_parent_in2[otherlabel].push_back(g1->getSig(IN_R2, other));
			// filtermap_parent_out2[otherlabel].push_back(g1->getSig(OUT_R2, other));

			if (!contains(in1, other)) {
				in1->insert(std::make_pair(other, core_len));
				t1in_len++;
				if (contains(out1, other))
					t1both_len++;
			}
		}

		for (int other : g1->getChildrenID(node1)) {

			// int otherlabel = g1->getVertexAttr(other);

			// filtermap_child_in1[otherlabel].push_back(g1->getSig(IN_R1, other));
			// filtermap_child_out1[otherlabel].push_back(g1->getSig(OUT_R1, other));
			// filtermap_child_in2[otherlabel].push_back(g1->getSig(IN_R2, other));
			// filtermap_child_out2[otherlabel].push_back(g1->getSig(OUT_R2, other));

			if (!contains(out1, other)) {
				out1->insert(std::make_pair(other, core_len));
				t1out_len++;
				if (contains(in1, other))
					t1both_len++;
			}
		}

		for (int other : g2->getParentsID(node2)) {
			if (!contains(in2, other)) {
				in2->insert(std::make_pair(other, core_len));
				t2in_len++;
				if (contains(out2, other))
					t2both_len++;
			}

			int olabel = g2->getVertexAttr(other);
			if ((!contains(sn2k, other)) && contains(labels, olabel)) {
				// if (matchAny(g2->getSig(IN_R1, other), filtermap_parent_in1.at(olabel)) &&
				//         matchAny(g2->getSig(OUT_R1, other), filtermap_parent_out1.at(olabel)) &&
				//         matchAny(g2->getSig(IN_R2, other), filtermap_parent_in2.at(olabel)) &&
				//         matchAny(g2->getSig(OUT_R2, other), filtermap_parent_out2.at(olabel))
				//    ) {
				// cout<<other<<std::endl;
				added_seen_n2.push_back(other);
				sn2k->insert(other);
				// }
			}
		}

		for (int other : g2->getChildrenID(node2)) {
			if (!contains(out2, other)) {
				out2->insert(std::make_pair(other, core_len));
				t2out_len++;
				if (contains(in2, other))
					t2both_len++;
			}
			int olabel = g2->getVertexAttr(other);
			if ((!contains(sn2k, other)) && contains(labels, olabel)) {
				// if (matchAny(g2->getSig(IN_R1, other), filtermap_child_in1.at(olabel)) &&
				//         matchAny(g2->getSig(OUT_R1, other), filtermap_child_out1.at(olabel)) &&
				//         matchAny(g2->getSig(IN_R2, other), filtermap_child_in2.at(olabel)) &&
				//         matchAny(g2->getSig(OUT_R2, other), filtermap_child_out2.at(olabel))
				//    ) {
				// cout<<other<<std::endl;
				added_seen_n2.push_back(other);
				sn2k->insert(other);
				// }
			}
		}

		sn2->insert(sn2->end(), added_seen_n2.begin(), added_seen_n2.end());
	}

	bool isGoal() {
		return core_len == gs1;
	}

	bool isDead() {
		return gs1 > gs2 || t1both_len > t2both_len || t1out_len > t2out_len
		       || t1in_len > t2in_len;
	}

	std::map<int, int> getMatch() {
		return *core1;
	}

	state copy() {
		return state(*this);
	}

	void backTrack() {

//		assert addedNode1 != NULL_NODE;
		if (orig_core_len < core_len) {

			int node2;

			if (in1->at(added_n1) == core_len)
				in1->erase(added_n1);

			for (int other : g1->getParentsID(added_n1)) {
				if (in1->at(other) == core_len)
					in1->erase(other);
			}

			if (out1->at(added_n1) == core_len)
				out1->erase(added_n1);

			for (int other : g1->getChildrenID(added_n1)) {
				if (out1->at(other) == core_len)
					out1->erase(other);
			}

			node2 = core1->at(added_n1);

			if (in2->at(node2) == core_len)
				in2->erase(node2);

			for (int other : g2->getParentsID(node2)) {
				if (contains(in2, other) && in2->at(other) == core_len)
					in2->erase(other);
			}

			if (out2->at(node2) == core_len)
				out2->erase(node2);

			for (int other : g2->getChildrenID(node2)) {
				if (contains(out2, other) && out2->at(other) == core_len)
					out2->erase(other);
			}

			core1->erase(added_n1);
			core2->erase(node2);

			//FIXME: caution!
			sn2->erase(sn2->end() - added_seen_n2.size(), sn2->end());
			for (int k = 0; k < added_seen_n2.size(); k++) {
				sn2k->erase(added_seen_n2[k]);
			}

			core_len = orig_core_len;
			added_n1 = NULL_NODE;
			added_seen_n2.clear();
		}
	}

private:
	Query<VD, ED> *g1; // as query graph
	Fragment<VD, ED> *g2; // as data graph

	int core_len = 0;
	int orig_core_len = 0;

	/** state information **/
	int t1both_len, t2both_len, t1in_len, t1out_len, t2in_len, t2out_len;

	std::map<int, int>* core1;
	std::map<int, int>* core2;
	std::map<int, int>* in1;
	std::map<int, int>* in2;
	std::map<int, int>* out1;
	std::map<int, int>* out2;

	std::vector<int>* sn2;
	std::set<int>* sn2k;

	std::set<int>* labels;

	int added_n1;
	std::vector<int> added_seen_n2;

	int gs1; // size of graph1
	int gs2; // size of graph2
};


std::mutex mtx;
template<class VD, class ED>
class vf2_inspector {
public:

	std::set<int> labelset;
	Query<VD, ED> *query;
	Fragment<VD, ED> *graph;

	vf2_inspector(Query<VD, ED>& _query, Fragment<VD, ED>& _graph): query(&_query), graph(&_graph) {
		for (auto v : query->getAllVerticesID()) {
			labelset.insert(query->getVertexAttr(v));
		}
	}

	std::set<std::map<int, int> > findEnumVF2Matches(int v1, int v2) {

		std::set<std::map<int, int> > matches;

		std::map<int, int> core1r;
		std::map<int, int> core2r;
		std::map<int, int> in1r;
		std::map<int, int> in2r;
		std::map<int, int> out1r;
		std::map<int, int> out2r;

		std::vector<int> sn2r;
		std::set<int> sn2kr;

		state<VD, ED> s(query, v1, graph, v2, core1r, core2r, in1r, in2r, out1r, out2r, sn2r, sn2kr, labelset);
		this->enumMatch(s, matches);
		return matches;
	}

	bool findDesignedVF2Matches(int v1, int v2) {

		std::set<int> matches;

		std::map<int, int> core1r;
		std::map<int, int> core2r;
		std::map<int, int> in1r;
		std::map<int, int> in2r;
		std::map<int, int> out1r;
		std::map<int, int> out2r;

		std::vector<int> sn2r;
		std::set<int> sn2kr;

		state<VD, ED> s(query, v1, graph, v2, core1r, core2r, in1r, in2r, out1r, out2r, sn2r, sn2kr, labelset);
		return this->matchAndNext(s, matches);
	}


	std::set<std::map<int, int> > findEnumVF2MatchesMultiThreads(int v1, std::unordered_set<int> v2_candidates, int thread_num) {

		std::set<std::map<int, int> > ms;
		std::set<std::map<int, int> > *msptr = &ms;

		ThreadPool pool(thread_num);

		for (int v2 : v2_candidates)
		{
			pool.Enqueue([v1, v2, this, msptr]() {
				try {
					std::set<std::map<int, int> > matches4one = this->findEnumVF2Matches(v1, v2);
					if (matches4one.size() != 0) {
						mtx.lock();
						msptr->insert(matches4one.begin(), matches4one.end());
						mtx.unlock();
					}
				} catch (...) {
					LOG(ERROR) << "vertex " << v2 << " should be verify." << std::endl;
				}
			});
		}
		return ms;
	}

	std::set<int> findDesignedVF2MatchesMultiThreads(int v1, std::unordered_set<int> v2_candidates, int thread_num) {

		std::set<int> ms;
		std::set<int> *msptr = &ms;

		ThreadPool pool(thread_num);

		for (int v2 : v2_candidates)
		{
			pool.Enqueue([v1, v2, this, msptr]() {
				try {
					bool v1match = this->findDesignedVF2Matches(v1, v2);
					if (v1match == true) {
						mtx.lock();
						msptr->insert(v2);
						mtx.unlock();
					}
				} catch (...) {
					LOG(ERROR) << "vertex " << v2 << " should be verify." << std::endl;
				}
			});
		}
		return ms;
	}

	std::string printMatch(std::map<int, int> m) {
		std::stringstream ss;
		ss << "[";
		for (std::map<int, int>::iterator it = m.begin(); it != m.end(); it++) {
			ss << it->first << "->" << it->second << ", ";
		}
		ss << "]" << std::endl;
		return ss.str();
	}



private:
	bool enumMatch(state<VD, ED>& s, std::set<std::map<int, int> >& matches) {

		if (s.isGoal()) {
			matches.insert(s.getMatch());
			return true;
		}

		if (s.isDead()) {
			return false;
		}

		int n1 = NULL_NODE, n2 = NULL_NODE;
		std::pair<int, int> next = std::make_pair(n1, n2);
		bool found = false;
		next = s.nextPair(n1, n2);
		while (true) {
			n1 = next.first;
			n2 = next.second;
			if (next.first == NULL_NODE && next.second == NULL_NODE) {
				break;
			}
			if (s.isFeasiblePair(n1, n2)) {
				state<VD, ED> copy = s.copy();
				copy.addPair(n1, n2);
				found = enumMatch(copy, matches);
				copy.backTrack();
			}
			next = s.nextPair(n1, n2);
		}
		return found;
	}

	bool matchAndNext(state<VD, ED>& s, std::set<int>& matches) {

		if (s.isGoal()) {
			return true;
		}

		if (s.isDead()) {
			return false;
		}

		int n1 = NULL_NODE, n2 = NULL_NODE;
		std::pair<int, int> next = std::make_pair(n1, n2);
		bool found = false;
		next = s.nextPair(n1, n2);
		while (true) {
			n1 = next.first;
			n2 = next.second;
			if (next.first == NULL_NODE && next.second == NULL_NODE) {
				break;
			}
			if (s.isFeasiblePair(n1, n2)) {
				state<VD, ED> copy = s.copy();
				copy.addPair(n1, n2);
				found = matchAndNext(copy, matches);
				if(!found){
					copy.backTrack();
				}
			}
			next = s.nextPair(n1, n2);
		}
		return found;
	}
};
